package com.leetcode.algorithm.y22.m09.w2;

import java.util.Arrays;

/**
 * 56. 合并区间
 * 
 * https://leetcode.cn/problems/merge-intervals/
 * 
 * @author jie.deng
 *
 */
class Question0056Solution02 {

	// 贪心算法
	public int[][] merge(int[][] intervals) {
		// 排序之后
		// 局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，
		// 整体最优：合并所有重叠的区间
		Arrays.sort(intervals, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0]));

		int len = intervals.length;
		int[][] ret = new int[len][2];
		int idx = 0;
		int left = intervals[0][0];
		int right = intervals[0][1];
		for (int i = 1; i < intervals.length; i++) {
			int[] arr = intervals[i];
			if (arr[0] > right) {
				ret[idx++] = new int[] { left, right };
				left = intervals[i][0];
				right = intervals[i][1];
			} else {
				right = Math.max(right, arr[1]);
			}
		}
		ret[idx++] = new int[] { left, right };
		return Arrays.copyOfRange(ret, 0, idx);
	}

}